//
//  Sort.m
//  arithmetic
//
//  Created by 王涵 on 2021/2/20.
//

#import "Sort.h"

@implementation Sort

/// 选择排序 选取数组中第一个或最后一个数作为基准，在从数组的其他元素中依次与基准值比较 选择一个最大的 或最小的 与基准值交换位置，
/// @param array --
+ (NSMutableArray *)selection:(NSMutableArray *)array {
    if(!array || array.count == 0 || array.count == 1){
        return array;
    }
    NSMutableArray *resultArray = [array mutableCopy];
    for (NSInteger i = 0; i<resultArray.count; i++) {
        NSInteger minIndex = i;
        for (NSInteger j = i+1; j<resultArray.count; j++) {
            if ([resultArray[minIndex] intValue] > [resultArray[j] intValue]) {
                minIndex = j;
            }
        }
        [resultArray exchangeObjectAtIndex:minIndex withObjectAtIndex:i];
    }
    NSLog(@"这里是选择排序结果--%@",resultArray);
    return resultArray;
}

+ (NSMutableArray *)bubble:(NSMutableArray *)array {
    if(!array || array.count == 0 || array.count == 1){
        return array;
    }
    NSMutableArray *resultArray = [array mutableCopy];
    
    for(NSInteger i=resultArray.count-1;i>=1;i--){
        NSInteger temp = i;//记录最后交换的位置
        for(NSInteger j=1; j<=i;j++){
            if([resultArray[j] intValue] < [resultArray[j-1] intValue]){
                [resultArray exchangeObjectAtIndex:j withObjectAtIndex:j-1];
                temp = j;
            }
        }
        i = temp;
    }
    NSLog(@"这里是优化的冒泡排序结果--%@",resultArray);
    return resultArray;
}
+ (NSMutableArray *)insertion:(NSMutableArray *)array {
    if(!array || array.count == 0 || array.count == 1){
        return array;
    }
    NSMutableArray *resultArray = [array mutableCopy];
    
    for(NSInteger i=1;i<resultArray.count;i++){
        NSInteger cur = i;
        while (cur>0 && [resultArray[cur] intValue] < [resultArray[cur-1] intValue]) {
            [resultArray exchangeObjectAtIndex:cur withObjectAtIndex:cur-1];
            cur--;
        }
    }

    NSLog(@"插入排序结果--%@",resultArray);
    
//    for(NSInteger i=1;i<resultArray.count;i++){
//        NSInteger cur = i;
//        id temp = resultArray[cur];
//        while (cur>0 && [resultArray[cur] intValue] < [resultArray[cur-1] intValue]) {
//            resultArray[cur] = resultArray[cur-1];
//            cur--;
//        }
//        resultArray[cur] = temp;
//    }
//    NSLog(@"优化插入排序结果--%@",resultArray);
    return resultArray;
}
+ (NSMutableArray *)shell:(NSMutableArray *)array {
    if(!array || array.count == 0 || array.count == 1){
        return array;
    }
    NSMutableArray *resultArray = [array mutableCopy];
    NSInteger number = resultArray.count/2;
    
    while (number >=1) {
        for (NSInteger i=0; i<resultArray.count; i++) {
            for (NSInteger j=number; j<resultArray.count-1; j++) {
                if([resultArray[j] intValue] <[resultArray[j-number] intValue]){
                    [resultArray exchangeObjectAtIndex:j withObjectAtIndex:j-number];
                }
            }
        }
        number = number/2;
    }
    
    NSLog(@"希尔排序结果--%@",resultArray);
    return resultArray;
}

+ (NSMutableArray *)quick:(NSMutableArray *)array {
    if(!array || array.count == 0 || array.count == 1){
        return array;
    }
    NSMutableArray *resultArray = [array mutableCopy];
    [self quickSortWithArray:resultArray leftIndex:0 rightIndex:resultArray.count-1];
    NSLog(@"快速排序结果--%@",resultArray);
    return resultArray;
}

+ (void)quickSortWithArray:(NSMutableArray *)array leftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex {
    if (leftIndex > rightIndex) {
        return;
    }
    NSInteger left = leftIndex;
    NSInteger right = rightIndex;
    id temp = array[left];
    while (left<right) {
        while (left<right && [array[right] intValue] >= [temp intValue]) {
            right--;
        }
        array[left] = array[right];
        while (left<right && [array[left]intValue] <= [temp intValue]) {
            left++;
        }
        array[right] = array[left];
    }
    array[left] = temp;
    [self quickSortWithArray:array leftIndex:leftIndex rightIndex:left-1];
    [self quickSortWithArray:array leftIndex:right+1 rightIndex:rightIndex];
}
+ (NSMutableArray *)merge:(NSMutableArray *)array {
    if(!array || array.count == 0 || array.count == 1){
        return array;
    }
    
    NSMutableArray *resultArray = [array mutableCopy];
    NSMutableArray *tempArray = [[NSMutableArray alloc] initWithCapacity:resultArray.count];
    [self mergeWithArray:resultArray lowIndex:0 hightIndex:resultArray.count-1 temp:tempArray];
    NSLog(@"归并排序结果--%@",resultArray);
    return resultArray;
}

+ (void)mergeWithArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex hightIndex:(NSInteger)hightIndex temp:(NSMutableArray *)tempArray{

    if (lowIndex<hightIndex) {
        NSInteger mid = (lowIndex + hightIndex)/2;
        [self mergeWithArray:array lowIndex:lowIndex hightIndex:mid temp:tempArray];
        [self mergeWithArray:array lowIndex:mid+1 hightIndex:hightIndex temp:tempArray];
        [self mergeSortWithArray:array lowIndex:lowIndex hightIndex:hightIndex midIndex:mid temp:tempArray];
        
    }
    
}


+ (void)mergeSortWithArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex hightIndex:(NSInteger)hightIndex midIndex:(NSInteger)midIndex temp:(NSMutableArray *)tempArray{
    tempArray = [[NSMutableArray alloc] initWithCapacity:array.count];
    NSInteger i = 0;
    NSInteger low = lowIndex;
    NSInteger mid = midIndex+1;

    while (low<=midIndex && mid<=hightIndex) {
        
        if ([array[low] intValue] < [array[mid] intValue]) {
            tempArray[i] = array[low];
            i++;
            low++;
        }else{
            tempArray[i] = array[mid];
            i++;
            mid++;
        }
    }
    
    while (low<=midIndex) {
        tempArray[i++] = array[low++];
    }
    
    while (mid<=hightIndex) {
        tempArray[i++] = array[mid++];
    }
    
    for (NSInteger t = 0; t<i; t++) {
        array[lowIndex+t] = tempArray[t];
    }
}

@end
